#include <stdio.h>
#include <stdlib.h>



void FixDown(int *arr,int size);



void FixUp(int *arr,int size,int index);



int main(int argc,char **argv)
{




	int i;

	int *arr=(int *)malloc(sizeof(int)*(argc-1));

	void HeapSort(int *arr,int size);

	for(i=1;i<argc;i++)
	{
		arr[i-1]=atoi(*(argv+i));
		printf("%d\t",arr[i-1]);
	
	}

	printf("\n");
	
		
	HeapSort(arr,argc-1);


	return 0;
}


void HeapSort(int *arr,int size)
{


	int i=0;
	int j=0;
	int swap=0;
	int *rarr=(int *)malloc(sizeof(int)*size);


	for(;i<size;i++)
	{
		rarr[i]=arr[i];
		FixUp(rarr,size,i);
	}


	 for(i=0;i<size;i++)
        {
		  printf("%d\t",rarr[i]);
        }


	i=size-1;
	while(i>0)
	{
		
		swap=rarr[0];
		rarr[0]=rarr[i];
		rarr[i]=swap;
		FixDown(rarr,i);

		 printf("\n");

         for(j=0;j<size;j++)
        {
                  printf("%d\t",rarr[j]);
        }

		i--;
	
	}

	printf("\n");

	 for(i=0;i<size;i++)
        {
                  printf("%d\t",rarr[i]);
        }



}	

void FixDown(int *arr,int size)
{


	int i=0;

	int child=0;

	int maxChild=0;
	int swap=0;

	while(2*(i+1)<=size)
	{
		
		if(2*(i+1)+1>size)
		{
			maxChild=2*(i+1)-1;	
		}
		else
		{
			maxChild=arr[2*(i+1)-1]>arr[2*(i+1)]
						?2*(i+1)-1:2*(i+1);
		}

	
		if(arr[i]>arr[maxChild])
		{
			break;
		}
	
		swap=arr[i];	
		arr[i]=arr[maxChild];
		arr[maxChild]=swap;		
		
		i=maxChild;
		
	}
	
	
}





void FixUp(int *arr,int size,int index)
{

	
	int swap=0;
	int pIndex=0;
	while(index+1>1)
	{

		pIndex=(index+1)/2-1;

		if(arr[index]<arr[pIndex])
		{
			break;
		}
		
		swap=arr[index];
		arr[index]=arr[pIndex];
		arr[pIndex]=swap;
			
		index=pIndex;
	}
	


}
